// Queue 队列
// 只允许一端插入数据，另一端删除数据
// 先进先出，FIFO原则
// 一般用链表来实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;

// 初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

// 队尾入,队头出
void QueuePush(Queue* pq, QDataType val);
void QueuePop(Queue* pq);

// 获取数据，判断是否为空
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool isQueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
    assert(pq);

    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);

    QNode* cur = pq->head;
    while (cur != NULL){
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType val)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL){
        printf("malloc fail\n");
        exit(-1);
    }

    newNode->data = val;
    newNode->next = NULL;

    if (pq->tail == NULL){
        pq->head = pq->tail = newNode;
    }
    else {
        pq->tail->next = newNode;
        pq->tail = newNode;
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);

    int size = 0;
    QNode* cur = pq->head;
    while(cur != NULL){
        size++;
        cur = cur->next;
    }

    return size;
}

bool isQueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->head == NULL;
}

int main(void)
{
    // 初始化
    Queue q;
    QueueInit(&q);

    // 队头出队尾入
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    printf("%d ", QueueFront(&q));
    putchar('\n');

    QueuePop(&q);
    printf("%d ", QueueFront(&q));
    putchar('\n');

    // 打印
    while (!isQueueEmpty(&q)){
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    putchar('\n');

    // 销毁
    QueueDestroy(&q);

    return 0;
}












